package algocasts;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P125_CourseScheduleII {
    private boolean hasCycle(List<List<Integer>> graph, boolean[] visited,
                             boolean[] checked, int v, List<Integer> list) {
        if (visited[v]) return true;
        visited[v] = true;
        for (Integer i : graph.get(v)) {
            if (!checked[i] && hasCycle(graph, visited, checked, i, list))
                return true;
        }
        checked[v] = true;
        list.add(v);
        visited[v] = false;
        return false;
    }

    public int[] findOrder(int n, int[][] pairs) {
        List<List<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());
        for (int[] pair : pairs) {
            graph.get(pair[1]).add(pair[0]);
        }

        boolean[] checked = new boolean[n];
        boolean[] visited = new boolean[n];
        List<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            if (!checked[i] && hasCycle(graph, visited, checked, i, list))
                return new int[]{};
        }

        int[] order = new int[n];
        for (Integer i : list)
            order[--n] = i;
        return order;
    }


    public int[] canFinish_TopoSortAdjList(int n, int[][] pairs) {
        int[] inDegree = new int[n];
        List<List<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());

        for (int[] pair : pairs) {
            graph.get(pair[1]).add(pair[0]);
            ++inDegree[pair[0]];
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++)
            if (inDegree[i] == 0) q.add(i);

        int[] order = new int[n];
        int size = 0;
        while (!q.isEmpty()) {
            int v = q.poll();
            order[size++] = v;
            for (Integer i : graph.get(v)) {
                --inDegree[i];
                if (inDegree[i] == 0) q.add(i);
            }
        }
        return size == n ? order : new int[]{};
    }

}
